๐Ÿ‘ฉโ€๐Ÿ’ป 43163. ๋‹จ์–ด ๋ณ€ํ™˜

@Seongukbaek Posted April 12, 2022 ยท Updated April 12, 2022 ยท 4 min read

๋ฌธ์ œ

๋‘ ๊ฐœ์˜ ๋‹จ์–ด begin, target๊ณผ ๋‹จ์–ด์˜ ์ง‘ํ•ฉ words๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค. ์•„๋ž˜์™€ ๊ฐ™์€ ๊ทœ์น™์„ ์ด์šฉํ•˜์—ฌ begin์—์„œ target์œผ๋กœ ๋ณ€ํ™˜ํ•˜๋Š” ๊ฐ€์žฅ ์งง์€ ๋ณ€ํ™˜ ๊ณผ์ •์„ ์ฐพ์œผ๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

  1. ํ•œ ๋ฒˆ์— ํ•œ ๊ฐœ์˜ ์•ŒํŒŒ๋ฒณ๋งŒ ๋ฐ”๊ฟ€ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
  2. words์— ์žˆ๋Š” ๋‹จ์–ด๋กœ๋งŒ ๋ณ€ํ™˜ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด begin์ด "hit", target๊ฐ€ "cog", words๊ฐ€ ["hot","dot","dog","lot","log","cog"]๋ผ๋ฉด "hit" -> "hot" -> "dot" -> "dog" -> "cog"์™€ ๊ฐ™์ด 4๋‹จ๊ณ„๋ฅผ ๊ฑฐ์ณ ๋ณ€ํ™˜ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๋‘ ๊ฐœ์˜ ๋‹จ์–ด begin, target๊ณผ ๋‹จ์–ด์˜ ์ง‘ํ•ฉ words๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ์ตœ์†Œ ๋ช‡ ๋‹จ๊ณ„์˜ ๊ณผ์ •์„ ๊ฑฐ์ณ begin์„ target์œผ๋กœ ๋ณ€ํ™˜ํ•  ์ˆ˜ ์žˆ๋Š”์ง€ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•ด์ฃผ์„ธ์š”.

์ œํ•œ์‚ฌํ•ญ

  • ๊ฐ ๋‹จ์–ด๋Š” ์•ŒํŒŒ๋ฒณ ์†Œ๋ฌธ์ž๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ ์žˆ์Šต๋‹ˆ๋‹ค.
  • ๊ฐ ๋‹จ์–ด์˜ ๊ธธ์ด๋Š” 3 ์ด์ƒ 10 ์ดํ•˜์ด๋ฉฐ ๋ชจ๋“  ๋‹จ์–ด์˜ ๊ธธ์ด๋Š” ๊ฐ™์Šต๋‹ˆ๋‹ค.
  • words์—๋Š” 3๊ฐœ ์ด์ƒ 50๊ฐœ ์ดํ•˜์˜ ๋‹จ์–ด๊ฐ€ ์žˆ์œผ๋ฉฐ ์ค‘๋ณต๋˜๋Š” ๋‹จ์–ด๋Š” ์—†์Šต๋‹ˆ๋‹ค.
  • begin๊ณผ target์€ ๊ฐ™์ง€ ์•Š์Šต๋‹ˆ๋‹ค.
  • ๋ณ€ํ™˜ํ•  ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ์—๋Š” 0๋ฅผ return ํ•ฉ๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

begin target words return
"hit" "cog" ["hot", "dot", "dog", "lot", "log", "cog"] 4
"hit" "cog" ["hot", "dot", "dog", "lot", "log"] 0

๐Ÿ“ Logic

private int dfs(String begin, String target, String[] words, boolean[] visited, int count, int idx) { if (begin.equals(target) || visited[idx]) return count; visited[idx] = true; int ans = 0; for (int i = 0; i < words.length; i++) { if (idx != i && !visited[i] && isOneCharDiff(begin, words[i])) ans = dfs(words[i], target, words, visited, count + 1, i); } return ans; }
  • ์žฌ๊ท€์ ์ธ DFS๋ฅผ ์ด์šฉํ•ด ํ˜„์žฌ ๋‹จ์–ด์™€ ํ•œ ๋ฌธ์ž๋งŒ ๋‹ค๋ฅธ ๋‹จ์–ด๋กœ ๋ณ€ํ™˜์„ ์ˆ˜ํ–‰ํ•œ๋‹ค.

    • ์ด๋•Œ ์ง€๊ธˆ๊นŒ์ง€์˜ ๋ณ€ํ™˜๋œ ์ˆ˜(count)๋ฅผ ํ•จ๊ป˜ ์ „๋‹ฌํ•œ๋‹ค.

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.util.*; class Solution { public int solution(String begin, String target, String[] words) { boolean[] visited; int answer = words.length + 1; for (int i = 0; i < words.length; i++) { visited = new boolean[words.length]; if (isOneCharDiff(begin, words[i])) answer = Math.min(answer, dfs(words[i], target, words, visited, 1, i)); } if (answer == words.length + 1) return 0; return answer; } private int dfs(String begin, String target, String[] words, boolean[] visited, int count, int idx) { if (begin.equals(target) || visited[idx]) return count; visited[idx] = true; int ans = 0; for (int i = 0; i < words.length; i++) { if (idx != i && !visited[i] && isOneCharDiff(begin, words[i])) ans = dfs(words[i], target, words, visited, count + 1, i); } return ans; } private boolean isOneCharDiff(String str1, String str2) { int count = 0; for (int i = 0; i < str1.length() && count < 2; i++) if (str1.charAt(i) != str2.charAt(i)) count++; return count == 1; } }

โœ๏ธ Review

  • ๋‹จ์–ด๋ณ„ ๋‹ค๋ฅธ ๋ฌธ์ž ์ˆ˜๋ฅผ ๊ทธ๋ž˜ํ”„ ํ˜•ํƒœ๋กœ ๋ณ€ํ™˜ํ•ด ์ €์žฅํ•˜๊ณ  ์ด๋ฅผ BFS ๋ฐฉ์‹์œผ๋กœ ์ ‘๊ทผํ•˜๋„๋ก ๊ตฌํ˜„ํ–ˆ๋Š”๋ฐ, ๋ฐฉ๋ฒ• ์ž์ฒด๊ฐ€ ์ž˜๋ชป ๋œ ๊ฒƒ ๊ฐ™์•˜๋‹ค.
  • ํ•œ ๋ฌธ์ž๋งŒ ๋‹ค๋ฅธ ๋‹จ์–ด๋กœ ๋ณ€ํ™˜ํ•  ์ˆ˜ ์žˆ๊ธฐ์— ๊ตณ์ด ๋‹จ์–ด๋ณ„ ๋‹ค๋ฅธ ๋ฌธ์ž ์ˆ˜๋ฅผ ๊ตฌํ•  ํ•„์š”๊ฐ€ ์—†์—ˆ๊ณ  DFS๋ฅผ ์ด์šฉํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ์ฐธ๊ณ ํ–ˆ๋‹ค.

๐Ÿ“• ์ถœ์ฒ˜

Programmers : https://programmers.co.kr/learn/courses/30/lessons/43163

@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€